package struct;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class AllOne {

    private final Bucket head;
    private final Bucket tail;

    private final Map<String, Bucket> buckets;

    public class Bucket {
        public int count;
        public Bucket prev;
        public Bucket next;
        public Set<String> stringSet;

        public Bucket(String string, Bucket prev, Bucket next) {
            this.stringSet = new HashSet<>();
            stringSet.add(string);
            this.next = next;
            this.prev = prev;
        }

        public void add(String key) {
            this.stringSet.add(key);
        }

        public Bucket(String string, int count) {
            this.stringSet = new HashSet<>();
            stringSet.add(string);
            this.count = count;
        }

        public void remove() {
            Bucket prev = this.prev;
            Bucket next = this.next;
            prev.next = next;
            next.prev = prev;
        }

        public void linkedLast(Bucket bucket) {
            bucket.prev = this;
            bucket.next = this.next;
            this.next.prev = bucket;
            this.next = bucket;
        }

        public void linkedPrev(Bucket bucket) {
            bucket.prev = this.prev;
            bucket.next = this;
            this.prev.next = bucket;
            this.prev = bucket;
        }

    }

    public AllOne() {
        head = new Bucket("", 0);
        tail = new Bucket("", Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;

        buckets = new HashMap<>();
    }

    public void inc(String key) {
        Bucket storeBucket;
        if (!buckets.containsKey(key)) {
            Bucket oneBucket = head.next;
            if (oneBucket.count != 1) {
                // 不为 1 更新
                storeBucket = new Bucket(key, 1);
                head.linkedLast(storeBucket);
            } else {
                head.next.stringSet.add(key);
                storeBucket = head.next;
            }
        } else {
            Bucket curBucket = buckets.get(key);
            int count = curBucket.count;
            // 次数桶不存在
            if (curBucket.next.count != count + 1) {
                storeBucket = new Bucket(key, count + 1);
                curBucket.linkedLast(storeBucket);
            } else {
                // 次数桶存在
                storeBucket = curBucket.next;
                storeBucket.stringSet.add(key);
            }
            // 为空移除当前桶
            curBucket.stringSet.remove(key);
            if (curBucket.stringSet.isEmpty()) {
                curBucket.remove();
            }

        }
        buckets.put(key, storeBucket);
    }

    public void dec(String key) {
        if (!buckets.containsKey(key)) {
            return;
        }

        Bucket storeBucket = buckets.get(key);
        Bucket newBucket = storeBucket.prev;
        int count = storeBucket.count;
        storeBucket.stringSet.remove(key);

        if (newBucket.count == count - 1) {
            newBucket.stringSet.add(key);
        } else {
            newBucket = new Bucket(key, count - 1);
            storeBucket.linkedPrev(newBucket);
        }

        // 次数为 1
        if (count == 1) {
            buckets.remove(key);
        }
        // 当前桶只有一个元素
        if (storeBucket.stringSet.isEmpty()) {
            storeBucket.remove();
        }

        buckets.put(key, newBucket);
    }

    public String getMaxKey() {
        return tail.prev.stringSet.iterator().next();
    }

    public String getMinKey() {
        return head.next.stringSet.iterator().next();
    }


    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("hello");
        allOne.inc("hello");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
        allOne.dec("hello");
        allOne.dec("hello");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
    }

}
